package 第四周;

/*
 * @author  YxinMiracle
 * @date  2022-04-30 9:24
 * @Gitee: https://gitee.com/yxinmiracle
 */

/// 使用最小堆进行解答

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Node {
    int val;
    ListNode listNode;

    Node(int val, ListNode listNode) {
        this.val = val;
        this.listNode = listNode;
    }
}

// 最小堆 里面使用list进行实现
class BinaryHeap {
    List<Node> queue;

    BinaryHeap() {  // init BinaryHeap
        this.queue = new ArrayList<>();
        queue.add(new Node(0, new ListNode())); // 浪费第0个位置
    }

    public void insertNode(Node newNode) {
        queue.add(newNode);
        int newNodeIndex = queue.size() - 1; // 新Node的下标

        // 需要实现最小堆，那我应该把小的放在最前面，如果当前node的值，比他父亲的要小，那么就进行交换，移到前面去
        while (newNodeIndex > 1){
            if (this.queue.get(newNodeIndex).val < this.queue.get(newNodeIndex / 2).val){
                Node parentNode = this.queue.get(newNodeIndex / 2); // 把父亲的数据拿到手
                Node node = this.queue.get(newNodeIndex); // 把父亲的数据拿到手
                // 把父亲的数据拿到手后进行交换
                this.queue.set(newNodeIndex, parentNode);
                this.queue.set(newNodeIndex / 2, node);
                newNodeIndex /= 2;
            }else {
                break;
            }
        }

    }

    public boolean isEmpty() {
        return this.queue.size() == 1;
    }


    /**
     * 取出堆头
     * 需要将堆头跟堆尾进行交换
     *
     * @return
     */
    public Node pop() {
        Node headNode = this.queue.get(1);
        Node tailNode = this.queue.get(this.queue.size() - 1);

        this.queue.set(1, tailNode);
        this.queue.remove(this.queue.size() - 1); //移除最后一个元素，也就是一开始的堆头元素
        heapifyDown(1);
        return headNode;
    }

    void heapifyDown(int p){
        int child = p * 2;
        while (child < this.queue.size()){
            int other = p * 2 + 1;
            if (other < this.queue.size() && this.queue.get(other).val < this.queue.get(child).val)
                child = other;
            if (this.queue.get(child).val < this.queue.get(p).val){
                Node temp = this.queue.get(child);
                this.queue.set(child,this.queue.get(p));
                this.queue.set(p,temp);
                p = child;
                child = p * 2;
            }else break;
        }
    }
}

public class 合并K个升序链表 {

    public ListNode mergeKLists(ListNode[] lists) {
        BinaryHeap binaryHeap = new BinaryHeap();
        ListNode ans = new ListNode();
        ListNode tail = ans;
        for (ListNode listNode : lists) {
            if (listNode == null) continue;
            binaryHeap.insertNode(new Node(listNode.val, listNode));
        }
        // 先进行一轮排序,如果不等于空，那么就进行接下来的操作
        while (!binaryHeap.isEmpty()) {
            // 需要取出堆头，添加到ans中
            Node node = binaryHeap.pop();
            tail.next = new ListNode(node.val);
            tail = tail.next;
            if (node.listNode.next != null) binaryHeap.insertNode(new Node(node.listNode.next.val, node.listNode.next));
        }
        return ans.next;
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        System.out.println(list.get(3));
    }

}
